﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm.Middle_2104_SubArrayRanges
{
    class MainProject
    {
        static void Main(string[] args)
        {
            Console.WriteLine(SubArrayRanges(new int[] { 4, -2, -3, 4, 1 }));
            Console.ReadKey();
        }
        public static long SubArrayRanges(int[] nums)
        {

            #region 自己做的可以优化

            //双指针+暴力
            //if (nums.Length == 1) return nums[0];

            //int firstIndex = 0;
            //int secondIndex = 0;

            //int maxValue = 0;
            //int minValue = 0;

            //long sum = 0;
            //for (int i = 0; i < nums.Length; i++)
            //{
            //    firstIndex = i;
            //    secondIndex = i + 1;
            //    if (secondIndex >= nums.Length) break;
            //    if (nums[firstIndex] > nums[secondIndex])
            //    {
            //        maxValue = nums[firstIndex];
            //        minValue = nums[secondIndex];
            //    }
            //    else
            //    {
            //        minValue = nums[firstIndex];
            //        maxValue = nums[secondIndex];
            //    }
            //    while (secondIndex < nums.Length)
            //    {
            //        sum += maxValue - minValue;
            //        secondIndex++;
            //        if (secondIndex >= nums.Length) break;
            //        maxValue = Math.Max(maxValue, nums[secondIndex]);
            //        minValue = Math.Min(minValue, nums[secondIndex]);
            //    }
            //}
            //return sum;
            #endregion

            #region 优化后
            //int n = nums.Length;
            //long ret = 0;
            //for (int i = 0; i < n; i++)
            //{
            //    int minVal = int.MaxValue, maxVal = int.MinValue;
            //    for (int j = i; j < n; j++)
            //    {
            //        minVal = Math.Min(minVal, nums[j]);
            //        maxVal = Math.Max(maxVal, nums[j]);
            //        ret += maxVal - minVal;
            //    }
            //}
            //return ret;
            #endregion

            #region 单调栈(不理解)

            return SumMaxs(nums) - SumMins(nums);
            #endregion


        }

        private static long SumMins(int[] nums)
        {
            int len = nums.Length;
            int[] prevSmaller = new int[len];
            int[] nextSmaller = new int[len];

            Stack<int> stack = new Stack<int>();

            for (int i = 0; i < len; i++)
            {
                while (stack.Count!=0 && nums[stack.Peek()]>=nums[i])
                {
                    stack.Pop();
                }

                prevSmaller[i] = stack.Count == 0 ? -1 : stack.Peek();

                stack.Push(i);
            }
            stack.Clear();

            for (int i = len-1; i >=0; i--)
            {
                while (stack.Count != 0 && nums[stack.Peek()] > nums[i])
                {
                    stack.Pop();
                }

                nextSmaller[i] = stack.Count == 0 ? len : stack.Peek();

                stack.Push(i);
            }

            stack.Clear();

            long ans = 0;
            for (int i = 0; i < len; i++)
            {
                ans += (long)nums[i] * ((i - prevSmaller[i]) * (nextSmaller[i] - i));
            }
            return ans;
        }


        private static long SumMaxs(int[] nums)
        {
            int len = nums.Length;
            int[] prevBigger = new int[len];
            int[] nextBigger = new int[len];

            Stack<int> stack = new Stack<int>();

            for (int i = 0; i < len; i++)
            {
                while (stack.Count != 0 && nums[stack.Peek()] <= nums[i])
                {
                    stack.Pop();
                }

                prevBigger[i] = stack.Count == 0 ? -1 : stack.Peek();

                stack.Push(i);
            }
            stack.Clear();

            for (int i = len - 1; i >= 0; i--)
            {
                while (stack.Count != 0 && nums[stack.Peek()] < nums[i])
                {
                    stack.Pop();
                }

                nextBigger[i] = stack.Count == 0 ? len : stack.Peek();

                stack.Push(i);
            }

            stack.Clear();

            long ans = 0;
            for (int i = 0; i < len; i++)
            {
                ans += (long)nums[i] * ((i - prevBigger[i]) * (nextBigger[i] - i));
            }
            return ans;
        }
    }
}
